7613. Черное и белое

Жюри имеет большую художественную идею – создать прямоугольное полотно из большого количества черных и белых квадратов одинакового размера. Полотно должно содержать в точности b 4-связных областей из черных плиток и w 4-связных областей из белых плиток.

Напомним, что 4-связной областью некоторого цвета называется такой максимальный набор плиток, что:

· любые две плитки области имеют один и тот же цвет;

· для любых двух плиток области существует такая соединяющая их последовательность плиток, что любые две последовательные плитки имеют общую сторону.

В дополнение к художественной идее, жюри уже разработало программу, которая производит дизайн полотна. Но так как эта проблема касается искусства, то любое новое решение является чрезвычайно важным для жюри.

Вход. В одной строке содержатся два целых числа b и w (1 ≤ b, w ≤ 1000) – количество черных и белых областей.

Выход. В первой строке вывести размер картины r и c (1 ≤ r, c ≤ 100 000) – количество строк и столбцов. Далее следуют r строк по c символов в каждой. Каждый символ должен быть либо '@' (черная плитка) либо '.' (белая плитка). В полотне должно находиться не более 100 000 плиток.

Пример входа	Пример выхода
2 3	4 6 .@.@@@ @@@@@@ ...... .@....

РЕШЕНИЕ

математика - конструктив

Анализ алгоритма

В задаче следует построить картину, содержащую в точности b 4-связных областей из черных плиток и w 4-связных областей из белых плиток. Опишем один из возможных методов построения такой картины.

Картина будет иметь размер 4 на z = 2*max(b, w). Пусть, например b = 4, w = 6.

Вторая строка будет заполнена символами '@', третья – символами '.'. В первой строке сначала запишем w – 1 пар '.@', затем дополним строку символами '@'. В четвертой строке сначала запишем b – 1 пар '.@', затем дополним строку символами '.'.

Реализация алгоритма

Картину будем строить в символьном массиве s.

char s[4][3000];

Обнуляем массив s. Читаем входные данные.

memset(s,0,sizeof(s));

scanf("%d %d",&b,&w);

Вычисляем и выводим размер картины.

z = max(b,w) * 2;

printf("%d %d\n",4,z);

Строим первую строку.

for(i = 0; i < w - 1; i++)

{

s[0][2*i] = '.'; s[0][2*i+1] = '@';

}

for(i = 2*w - 2; i < z; i++)

s[0][i] = '@';

Строим вторую и третью строку.

for(i = 0; i < z; i++)

{

s[1][i] = '@'; s[2][i] = '.';

}

Строим четвертую строку.

for(i = 0; i < b - 1; i++)

{

s[3][2*i] = '.'; s[3][2*i+1] = '@';

}

for(i = 2*b - 2; i < z; i++)

s[3][i] = '.';

Выводим картину.

puts(s[0]); puts(s[1]); puts(s[2]); puts(s[3]);